home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / Dylan Related / Mindy / Mindy 1.2 - portable sources / libraries / coll-ext / vecsearch.dylan < prev   
Encoding:
Text File  |  1995-03-15  |  3.4 KB  |  82 lines  |  [TEXT/ttxt]
  1. module:     vector-search
  2. rcs-header:    $Header&
  3. author:     Robert Stockton (rgs@cs.cmu.edu)
  4. synopsis:    Provides a small assortment of specialized operations for
  5.         searching and modifying <vector>s.  These
  6.         operations are analogous to existing collection operations but
  7.         provide keywords and efficiency improvements which are
  8.         meaningful only within the more limited domain.
  9.  
  10. //======================================================================
  11. //
  12. // Copyright (c) 1994  Carnegie Mellon University
  13. // All rights reserved.
  14. // 
  15. // Use and copying of this software and preparation of derivative
  16. // works based on this software are permitted, including commercial
  17. // use, provided that the following conditions are observed:
  18. // 
  19. // 1. This copyright notice must be retained in full on any copies
  20. //    and on appropriate parts of any derivative works.
  21. // 2. Documentation (paper or online) accompanying any system that
  22. //    incorporates this software, or any part of it, must acknowledge
  23. //    the contribution of the Gwydion Project at Carnegie Mellon
  24. //    University.
  25. // 
  26. // This software is made available "as is".  Neither the authors nor
  27. // Carnegie Mellon University make any warranty about the software,
  28. // its performance, or its conformity to any specification.
  29. // 
  30. // Bug reports, questions, comments, and suggestions should be sent by
  31. // E-mail to the Internet address "gwydion-bugs@cs.cmu.edu".
  32. //
  33. //======================================================================
  34.  
  35. //======================================================================
  36. // The "string-search" module provides basic search and replace capabilities
  37. // upon restricted subsets of <sequence> -- primarily <vector>.
  38. // Exploiting the known properties of these types yields
  39. // substantially better performance than can be achieved for sequences in
  40. // general.  
  41. // 
  42. // The following functions are supplied:  
  43. // 
  44. // find-first-key vector predicate? #key start end failure => key 
  45. //     Find the index of first element (after start but before end) of a
  46. //     vector which satisfies the given predicate.  If no matching element is
  47. //     found, return failure.  The defaults for start, end and failure are,
  48. //     respectively,  0, size(vector), and #f.  This function is like
  49. //     find-key, but accepts start: and end: rather than skip:.) 
  50. // 
  51. // find-last-key vector predicate? #key start end failure => key 
  52. //     This is like find-first-key, but goes backward from end.  
  53. //======================================================================
  54.  
  55. // Find the index of first element (after "from") of a vector which
  56. // satisfies the given predicate.  (Like find-key, but accepts start: and end:
  57. // rather than skip:.)
  58. define method find-first-key(seq :: <vector>, pred?, 
  59.                  #key start = 0, end: last, failure: fail)
  60.   block (return)
  61.     let sz = size(seq);
  62.     let last = if (last & last < sz) last else sz end if;
  63.     for (i :: <fixed-integer> from start below last)
  64.       if (pred?(seq[i])) return(i) end if;
  65.     finally fail
  66.     end for
  67.   end block 
  68. end method find-first-key;
  69.  
  70. // Like find-first-key, but goes backward from the end (or from before end:).
  71. define method find-last-key(seq :: <vector>, pred?,
  72.                 #key start = 0, end: last, failure: fail)
  73.   block (return)  
  74.     let sz = size(seq);
  75.     let last = if (last & last < sz) last else sz end if;
  76.     for (i from last - 1 to start by -1) 
  77.       if (pred?(seq[i])) return(i) end if;
  78.     finally fail 
  79.     end for
  80.   end block 
  81. end method find-last-key;
  82.